# importamos las cosas que vamos a usar de aima
from search import Problem, astar_search

class ProblemaPuzzle(Problem):
    ''' Clase problema (formalizacion de nuestro problema) siguiendo la
        estructura que aima espera que tengan los problemas.'''

    def __init__(self, initial, goal=None):
        '''Inicializacion de nuestro problema.'''
        Problem.__init__(self, initial, goal)
        self._actions = [('Up',-1,0), ('Down',1, 0), ('Left',0,-1), ('Right',0,1)]

    def actions(self, s):
        '''Devuelve las acciones validas para un estado.'''
        # las acciones validas para un estado son aquellas que al aplicarse nos dejan en otro estado valido
        return [a for a in self._actions if self._is_valid(self.dest_espacio(s[1][0],s[1][1],a))]

    def _is_valid(self, p):
        '''Determina si un estado es valido o no.'''
        return (0<=p[0]<=2 and 0<=p[1]<=2)

    def Manhattan(self,n):
        s=list(n.state)
        m=0
        for i in s[0]:
            y=s[0].index(i)
            for p in i:
                x=i.index(p)
                m=m+ self.distancia_M(p,x,y)
        return m
    
    def distancia_M(self,num,x,y):
        g=list(self.goal)
        for i in g[0]:
            yy=g[0].index(i)
            for p in i:
                xx=i.index(p)
                if num==p:
                    return (abs(x-xx) + abs(y-yy))
                    

    def Brooklyng(self,n):
        '''Heuristica pensada por nosotros es similar a Manhattan(de ahi el nombre :p, solo que mide la distancia
        como si se tratara de una lista de 8 casilleros y no una matriz'''
        s=list(n.state)
        m=0
        for i in s[0]:
            y=s[0].index(i)
            for p in i:
                x=i.index(p)
                m=m+ self.distancia_B(p,x+y*3) #coordenada de la hipotetica lista
        return m

    def distancia_B(self,num,x):
        g=list(self.goal)
        for i in g[0]:
            yy=g[0].index(i)
            for p in i:
                xx=i.index(p)+yy*3
                if num==p:
                    return (abs(x-xx))
        
    def dest_espacio(self,x,y,a):
        return x+a[1], y+a[2]

    def result(self, s, a):
        '''Devuelve el estado resultante de aplicar una accion a un estado determinado.'''
        x,y = list(s[1])
        x1,y1 = self.dest_espacio(x,y,a)
        saux=(s[0][:],s[1])

        saux0=list(saux[0][0])
        saux1=list(saux[0][1])
        saux2=list(saux[0][2])
        saux_coord=list(saux[1])
        
        saux=[[saux0,saux1,saux2],saux_coord]
        saux[0][x][y],saux[0][x1][y1] = saux[0][x1][y1],saux[0][x][y]
        saux[1][0]=x1
        saux[1][1]=y1
        return (((saux[0][0][0],saux[0][0][1],saux[0][0][2]),(saux[0][1][0],saux[0][1][1],saux[0][1][2]),(saux[0][2][0],saux[0][2][1],saux[0][2][2])),(saux[1][0],saux[1][1]))

# creamos un problema a partir de nuestra formalizacion de ProblemaMisioneros
# como parametros le pasamos el estado inicial, y el estado meta que esperamos
EI=(((7,2,4),(5,0,6),(8,3,1)),(1,1))
EM=(((0,1,2),(3,4,5),(6,7,8)),(0,0))

p1 = ProblemaPuzzle(EI,EM)


# le decimos a aima que resuelva nuestro problema con el metodo de busqueda en
# amplitud
print 'Pensando...'
r =  astar_search(p1, p1.Manhattan)
# esto nos devuelve el nodo meta del arbol. Podemos recorrer sus padres para
# tener todo el camino de acciones
camino_acciones = []
while r:
    if r.action:
        camino_acciones.append(r.action[0])
    r = r.parent

print ' '.join(reversed(camino_acciones)) #se invierte porque se va obteniendo al reves
